package day190826;

import java.util.HashSet;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/8/26 下午 04:54
 */
public class ListNodeReverse {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    static ListNode STATIC_LIST;

    static {
        STATIC_LIST = new ListNode(1);
        STATIC_LIST.next = new ListNode(2);
        STATIC_LIST.next.next = new ListNode(3);
        STATIC_LIST.next.next.next = new ListNode(4);
        STATIC_LIST.next.next.next.next = new ListNode(5);
    }

    public static void main(String[] args) {
        ListNodeReverse nodeReverse = new ListNodeReverse();
//        ListNode beforeList = STATIC_LIST;
//        while (beforeList != null) {
//            System.out.print(beforeList.val + "->");
//            beforeList = beforeList.next;
//        }
//        System.out.println();
//        ListNode afterList = nodeReverse.reverseList(STATIC_LIST);
//        while (afterList != null) {
//            System.out.print(afterList.val + "->");
//            afterList = afterList.next;
//        }
//        System.out.println();
//        ListNode reverseListRecur = nodeReverse.reverseListRecur(STATIC_LIST);
//        while (reverseListRecur != null) {
//            System.out.print(reverseListRecur.val + "->");
//            reverseListRecur = reverseListRecur.next;
//        }
//        ListNode node = new ListNode(8);
//        ListNode next = STATIC_LIST.next;
//        STATIC_LIST.next = node;
//        node.next = next;
//        while (STATIC_LIST != null) {
//            System.out.print(STATIC_LIST.val + "->");
//            STATIC_LIST = STATIC_LIST.next;
//        }
        boolean hasLoop = nodeReverse.hasLoop2Recur(STATIC_LIST);
        System.out.println(hasLoop);
    }


    public boolean hasLoop(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == null) {
                return false;
            }
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    public boolean hasLoop2(ListNode head) {
        if (head == null) {
            return false;
        }
        HashSet<ListNode> hashSet = new HashSet<>();
        while (head != null) {
            if (hashSet.contains(head)) {
                return true;
            }
            hashSet.add(head);
            head = head.next;
        }
        return false;
    }

    HashSet<ListNode> hashSet = new HashSet<>();

    public boolean hasLoop2Recur(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        if (hashSet.contains(head)) {
            return true;
        } else {
            hashSet.add(head);
            return hasLoop2Recur(head.next);
        }
    }

    /**
     * 遍历反转法：从前往后反转各个结点的指针域的指向。
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        //上一结点
        ListNode preNode = head;
        //当前结点
        ListNode curNode = head.next;
        // 临时结点，用于保存当前结点的指针域（即下一结点）
        ListNode tmp;
        while (curNode != null) {
            tmp = curNode.next;
            //反转指向
            curNode.next = preNode;
            //向下移动
            preNode = curNode;
            curNode = tmp;
        }
        head.next = null;
        return preNode;
    }

    /**
     * 递归反转法：从尾结点开始，逆向反转各个结点的指针域指向。
     *
     * @param head
     * @return reverseHead
     */
    public ListNode reverseListRecur(ListNode head) {
        // head看作是前一结点，head.next 是当前结点，reverseHead是反转后新链表的头结点
        // 若为空链或者当前结点在尾结点，则直接还回
        if (head == null || head.next == null) {
            return head;
        }
        // 先反转后续结点 head.next
        ListNode reverseHead = reverseListRecur(head.next);
        // 将当前结点的指针域指向前一结点
        head.next.next = head;
        // 前一结点的指针域设为null;
        head.next = null;
        // 反转后新链表的头结点
        return reverseHead;
    }

    ListNode mergeOrderedList(ListNode list1, ListNode list2) {
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        //结果链表
        ListNode result = null;
        //结果链表中的最后一个结点，方便尾插
        ListNode tail = null;
        //保存遍历过程中的下一个结点
        ListNode next;
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                if (result != null) {
                    //结果链表不为空，直接在最后一个结点上做插入
                    //保存链表1的下一个结点，让循环继续
                    next = cur1.next;
                    //插入过程
                    tail.next = cur1;
                    cur1.next = null;
                    //保存新的最后一个结点
                    tail = cur1;
                    cur1 = next;
                } else {
                    //保存链表1的下一个结点，让循环继续
                    next = cur1.next;
                    result = cur1;
                    cur1.next = null;
                    //保存新的最后一个结点
                    tail = cur1;
                    cur1 = next;
                }
            } else {
                if (result != null) {
                    //结果链表不为空，直接在最后一个结点上做插入
                    //保存链表1的下一个结点，让循环继续
                    next = cur2.next;
                    //插入过程
                    tail.next = cur2;
                    cur2.next = null;
                    //保存新的最后一个结点
                    tail = cur2;
                    cur2 = next;
                } else {
                    //保存链表1的下一个结点，让循环继续
                    next = cur2.next;
                    result = cur2;
                    cur2.next = null;
                    //保存新的最后一个结点
                    tail = cur2;
                    cur2 = next;
                }
            }
        }
        //一个链表为空了
        if (cur1 == null) {
            tail.next = cur2;
        }
        if (cur2 == null) {
            tail.next = cur1;
        }
        return result;
    }

    public static ListNode mergeTwoList2(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 != null ? list1 : list2;
        }
        //合并后单链表头结点
        ListNode head = list1.val < list2.val ? list1 : list2;

        ListNode cur1 = head == list1 ? list1 : list2;
        ListNode cur2 = head == list1 ? list2 : list1;

        //cur1前一个元素
        ListNode pre = null;
        //cur2的后一个元素
        ListNode next = null;

        while (cur1 != null && cur2 != null) {
            //第一次进来肯定走这里
            if (cur1.val <= cur2.val) {
                pre = cur1;
                cur1 = cur1.next;
            } else {
                next = cur2.next;
                pre.next = cur2;
                cur2.next = cur1;
                pre = cur2;
                cur2 = next;
            }
        }
        pre.next = cur1 == null ? cur2 : cur1;
        return head;
    }

    public static ListNode mergeTwoList(ListNode list1, ListNode list2) {
        //递归结束条件
        if (list1 == null && list2 == null) {
            return null;
        }
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        //合并后的链表
        ListNode head = null;
        if (list1.val > list2.val) {
            //把head较小的结点给头结点
            head = list2;
            //继续递归head2
            head.next = mergeTwoList(list1, list2.next);
        } else {
            head = list1;
            head.next = mergeTwoList(list1.next, list2);
        }
        return head;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        //慢指针
        ListNode slow = head;
        //快指针
        ListNode fast = head;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
            if (fast == null) {
                break;
            }
        }
        if (fast == null) {
            head = head.next;
            return head;
        }
        //快指针没有到最后 继续向下遍历
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        //删除 slow 的下一个结点
        slow.next = slow.next.next;
        return head;
    }

    public static ListNode middleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 指向链表的头结点
        ListNode slow = head;
        // 指向链表的头结点的下一个结点
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return fast == null ? slow : slow.next;
    }

}
